package com.mid;

/**
 * Created by Lxk on 2019/5/26.
 */
public class Solution300 {

    public int lengthOfLIS(int[] nums) {
        int[] mem = new int[nums.length];
        for(int i = 0;i < nums.length; i++){
            mem[i] = 1;
        }
        for(int i = 1;i < nums.length ; i++){
            int max = 0;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j] && mem[j] + 1 > max){
                    max = mem[j] + 1;
                }
            }
            mem[i] = max == 0 ? 1 : max;
        }
        int max = 0;
        for(int val : mem){
            if(val > max){
                max = val;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,2,5,3,7,101,18};
        Solution300 solution300 = new Solution300();
        solution300.lengthOfLIS(arr);
    }

}
